package com.wzh.test;

/**
 * 八皇后问题
 * 8行8列的棋盘
 */
public class EeightQueenDemo {
    public static void main(String[] args) {

        //定义棋盘数组,0代表空，1代表已放，2代表有冲突不能放
        int[][] chessBoard = new int[8][8];
        int row = 0;
        int col = 0;
        System.out.println("==========初始化===============");
        printArray(chessBoard);
        put(chessBoard,0);
        System.out.println("============完成之后============");
        printArray(chessBoard);

    }

    public static boolean put(int[][] chessBoard,int row){
        boolean success = false;
        for(int k = 0; k < 8;k++){
            if(chessBoard[row][k] == 0){
                //可以放
                chessBoard[row][k] = 1;
                //把刚刚放好的这个位置所冲突的位置标记一下
                //每一行
                for (int i = row + 1; i < 8; i++) {
                    chessBoard[i][k] = 2;
                }
                //每一列
                for (int i = k + 1; i < 8; i++) {
                    chessBoard[row][i] = 2;
                }
                //左上角
                if (row > 0 && k > 0) {
                    chessBoard[row - 1][k - 1] = 2;
                }
                //右上角
                if (row > 0 && k < 7) {
                    chessBoard[row - 1][k + 1] = 2;
                }
                //左下角
                if(row < 7 && k > 0){
                    chessBoard[row + 1][k - 1] = 2;
                }
                //右下角
                if(row < 7 && k < 7){
                    chessBoard[row + 1][k + 1] = 2;
                }

                if(row < 7) {
                    //放下一行
                    boolean nextPut = put(chessBoard, row + 1);
                    if (nextPut) {
                        success = true;
                        break;
                    } else {
                        System.out.println("回溯");
                        //回溯
                        chessBoard[row][k] = 0;
                        //每一行
                        for (int i = row + 1; i < 8; i++) {
                            chessBoard[i][k] = 0;
                        }
                        //每一列
                        for (int i = k + 1; i < 8; i++) {
                            chessBoard[row][i] = 0;
                        }
                        //左上角
                        if (row > 0 && k > 0) {
                            chessBoard[row - 1][k - 1] = 0;
                        }
                        //右上角
                        if (row > 0 && k < 7) {
                            chessBoard[row - 1][k + 1] = 0;
                        }
                        //左下角
                        if (row < 7 && k > 0) {
                            chessBoard[row + 1][k - 1] = 0;
                        }
                        //右下角
                        if (row < 7 && k < 7) {
                            chessBoard[row + 1][k + 1] = 0;
                        }
                        continue;
                    }
                }else{
                    success = true;
                }
            }
            else if(chessBoard[row][k] == 2){
                continue;
            }
        }
        return success;
    }

    public static void printArray(int[][] maze) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(maze[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
